/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *start = head, *end = head, *prev = nullptr;
        int count = right - left + 1;
        while(--left)
        {
            prev = start;
            start = start->next;
        }

        while(--right)
            end = end->next;

        // 反转以start为起始指针的链表
        // 并且反转count次
        ListNode *n1 = end->next, *n2 = start, *n3 = start->next;

        while(count--)
        {
            n2->next = n1;

            n1 = n2;
            n2 = n3;

            if(n3)
                n3 = n3->next;
        }
        
        if(prev == nullptr)
            return n1;
        prev->next = n1;
        return head;
    }
};